import java.util.*;



public class Solution {
    public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */

    //方法一 迭代
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        LinkedList<ListNode> listNodes = new LinkedList<>();
        /*if(pHead1 == null){
            return pHead2;
        }
        if(pHead2 == null){
            return pHead1;
        }
        if(pHead2  == null && pHead1 == null){
            return  null;
        }*/
        // list1 list2为空的情况
        if(pHead1 == null || pHead2 == null){
            return pHead1 != null ? pHead1 : pHead2;
        }
        if(pHead1.val <= pHead2.val){
            pHead1.next = Merge(pHead1.next,pHead2);
            return pHead1;
        }
        else{
            pHead2.next = Merge(pHead1,pHead2.next);
            return pHead2;
        }
    }

    //2.借助额外数组
    public ListNode Merge2(ListNode pHead1, ListNode pHead2){
        if(pHead1 == null) return pHead2;
        if(pHead2 == null) return pHead1;
        if(pHead1 == null && pHead2 == null){
            return null;
        }
        //将两个链表存储在list中
        ArrayList<Integer> list = new ArrayList<>();
        //遍历存储pHead1
        while(pHead1 != null){
            list.add(pHead1.val);
            pHead1 = pHead1.next;
        }
        //遍历存储pHead2
        while(pHead2 != null){
            list.add(pHead2.val);
            pHead2 = pHead2.next;
        }
        //对list排序
        Collections.sort(list);
        //将list转换为链表
        ListNode newHead = new ListNode(list.get(0));
        ListNode cur = newHead;
        for(int i = 0; i < list.size(); i++){
            cur.next = new ListNode(list.get(i));
            cur = cur.next;
        }
        //合并输出链表
        return newHead;
    }

}